#include<bits/stdc++.h>
#define y1 Y1
#define fi first
#define endl "\n"
#define se second
#define PI acos(-1)
#define int long long
#define pb(x) push_back(x)
#define PII pair<int, int>
#define Yes cout << "Yes\n";
#define No cout << "No\n";
#define YES cout << "YES\n";
#define NO cout << "NO\n";
#define _for(i, a, b) for(int i = a; i <= b; ++i)
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;

const int N = 1e6 + 10;
int a[N], mod = 1e9 + 7;
int primes[N], cnt;
map<int, int>mp;
bool st[N];

void init(int n) {
	for(int i = 2; i <= n; ++ i ) {
		if(st[i] == false)primes[++cnt] = i;
		for(int j = 1; primes[j] <= n / i; ++ j ) {
			st[i * primes[j]] = true;
			if(i % primes[j] == 0)break;
		}
	}
}

signed main() {
	IOS;
	init(1000000);
	
	int n;
	cin >> n;
//	for(int i = 2; i <= n; ++ i ) {
//		int x = i;
//		for(int j = 1; primes[j] <= x; ++ j ) {
//			int t = 0;
//			if(x % primes[j] == 0) {
//				while(x % primes[j] == 0) {
//					t++;
//					x /= primes[j];
//				}
//				mp[primes[j]] += t;
//			} 
//		}
//		if(x > 1) {
//			mp[x]++;
//		}
//	}
   /* for(int i = 1; primes[i] <= n; ++ i ) {
    	int x = primes[i], ans = 0;
    //	cout << "x = " << x << endl;
    	while(x <= n) {
    		ans += n / x;
    		x = primes[i] * x;
    		//cout << "t = " << t << " tt = " << tt << endl;
		}
		cout << primes[i] << ' ' << ans << endl;
	}*/
	for(int i = 2; i <= n; ++ i ) {
		if(st[i])continue;
		int x = i, cnt = 0;
		while(x <= n) {
			cnt += n / x;
			x = x * i;
		}
		cout << i << ' ' << cnt << endl;
	} 
	
	return 0;
}



